|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ linked ： ・ list ： 名簿に記入する, 載る, 記入する, 一覧表, リスト, 表, 目録, ～を名簿に記入する, 傾く, 望む, 目録に載せる
Unrolled linked listは連結リストの変種で、各ノードに格納する要素を複数個にしたものである。CPUキャッシュの利用効率を劇的に向上させるとともに、リストのメタデータ（参照など）によるメモリ消費のオーバーヘッドを削減できる。B木とも関連がある。 ==概要== 典型的なUnrolled linked listの実装は以下のようになる。 record node 各ノードはある一定の最大個数（maxElements個）まで要素を格納できる。maxElementsの大きさは、1つのノードが1から数個程度のキャッシュラインに乗るように設定する。リスト中の要素の位置は、ノードへの参照と配列中の位置のペアで識別される。上記の実装に、リストの一つ前のノードへの参照を追加して、双方向のUnrolled linked listとすることもできる。 新しい要素を挿入する際は、要素が配置されるべきノードを探した上で、 elements配列に要素を挿入し、numElementsをインクリメントすればよい。配列がすでに一杯だった場合は、まず現在のノードの前か後ろのいずれかに新しいノードを挿入し、現在のノードの配列の内容の半分を新しいノードへ移動した上で、要素を配列へ追加する。要素を削除する場合も同様で、削除されるべき要素が入っているノードを探し、 elements配列から要素を削除し、numElementsをデクリメントする。numElementsがmaxElements÷2より小さくなった場合は、隣接ノードから現在のノードへ要素を移動させる。隣接ノードの要素もmaxElements÷2より少なかった場合は、要素を移動させてノードをひとつにまとめる。これにより、使用領域の無駄を省くことができる。抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Unrolled linked list」の詳細全文を読む スポンサード リンク
|